package cn.rocky.zuosheng;

import java.util.Stack;

/**
 * 题目: 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作
 *
 * 要求:
 *      1. pop、push、getMin 操作的时间复杂度都是O(1)
 *      2. 设计的栈类型可以使用现成的栈结构。
 * 第一种设计方案如下:
 *      压入数据规则:
 *      假设当前数据为 newNum, 先将其压入 stackData。然后判断 stackMin是否为空
 *      1. 如果为空, 则 newNum 也压入 stackMin
 *      2. 如果不为空, 则比较 newNum 和 stackMin 的栈顶元素中哪一个更小
 *      3. 如果newNum 更小或者两者相等, 则newNum也压入stackMin
 *      4. 如果 stackNum 中栈顶元素小, 则 stackMin 不压入任何内容
 *      弹出数据规则
 *
 */
public class MyStack1 {

    /**
     * 保存当前栈中的元素,其功能和一个正常的栈没有区别
     */
    private Stack<Integer> stackData;

    /**
     * 另一个栈用于保存每一步的最小值
     */
    private Stack<Integer> stackMin;

    public MyStack1() {
        this.stackData = new Stack<>();
        this.stackMin  = new Stack<>();
    }

    public void push(int newNum) {
        if (this.stackMin.isEmpty()) {
            this.stackMin.push(newNum);
        } else if (newNum <= this.getMin()) {
            this.stackMin.push(newNum);
        }
        this.stackData.push(newNum);
    }

    public int pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("your stack is empty.");
        }
        Integer value = this.stackData.pop();
        if (value == this.getMin()) {
            this.stackMin.pop();
        }
        return value;
    }

    public int getMin() {
        if (this.stackMin.isEmpty()) {
            throw new RuntimeException("your stack is empty.");
        }
        return this.stackMin.peek();
    }
}
